var bibbase_data = {"data":"\"Loading..\"\n\n
\n\n \n\n \n\n \n \n\n \n\n \n \n\n \n\n \n
\n generated by\n \n \"bibbase.org\"\n\n \n
\n \n\n
\n\n \n\n\n
\n\n Excellent! Next you can\n create a new website with this list, or\n embed it in an existing web page by copying & pasting\n any of the following snippets.\n\n
\n JavaScript\n (easiest)\n
\n \n <script src=\"https://bibbase.org/show?bib=https%3A%2F%2Fbibbase.org%2Fnetwork%2Ffiles%2Fe2kjGxYgtBo8SWSbC&authorFirst=1&nocache=1&fullnames=1&theme=bullets&group0=year&group1=type&owner={}&filter=tags:SDL&jsonp=1&jsonp=1\"></script>\n \n
\n\n PHP\n
\n \n <?php\n $contents = file_get_contents(\"https://bibbase.org/show?bib=https%3A%2F%2Fbibbase.org%2Fnetwork%2Ffiles%2Fe2kjGxYgtBo8SWSbC&authorFirst=1&nocache=1&fullnames=1&theme=bullets&group0=year&group1=type&owner={}&filter=tags:SDL&jsonp=1\");\n print_r($contents);\n ?>\n \n
\n\n iFrame\n (not recommended)\n
\n \n <iframe src=\"https://bibbase.org/show?bib=https%3A%2F%2Fbibbase.org%2Fnetwork%2Ffiles%2Fe2kjGxYgtBo8SWSbC&authorFirst=1&nocache=1&fullnames=1&theme=bullets&group0=year&group1=type&owner={}&filter=tags:SDL&jsonp=1\"></iframe>\n \n
\n\n

\n For more details see the documention.\n

\n
\n
\n\n
\n\n This is a preview! To use this list on your own web site\n or create a new web site from it,\n create a free account. The file will be added\n and you will be able to edit it in the File Manager.\n We will show you instructions once you've created your account.\n
\n\n
\n\n

To the site owner:

\n\n

Action required! Mendeley is changing its\n API. In order to keep using Mendeley with BibBase past April\n 14th, you need to:\n

    \n
  1. renew the authorization for BibBase on Mendeley, and
    2. \n
  2. update the BibBase URL\n in your page the same way you did when you initially set up\n this page.\n
    3. \n
\n

\n\n

\n \n \n Fix it now\n

\n
\n\n
\n\n\n
\n \n \n
\n
\n  \n 2022\n \n \n (1)\n \n \n
\n
\n \n \n
\n
\n  \n 4\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n Y. Mao; D. Data; S. N. Diggavi; and P. Tabuada.\n\n\n \n \n \n \n Decentralized Learning Robust to Data Poisoning Attacks.\n \n \n \n\n\n \n\n\n\n In IEEE Control and Decision Conference (CDC), 2022. \n \n\n\n\n
\n\n\n\n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@INPROCEEDINGS{mao2022decentralizedlearning,\n  title={Decentralized Learning Robust to Data Poisoning Attacks},\n  author={Mao, Y. and Data, D. and Diggavi, S. N. and Tabuada, P.},\n  booktitle={IEEE Control and Decision Conference (CDC)},\n  year={2022},\n  type={4},\n  tags={conf,SDL,DML},\n}\n\n
\n
\n\n\n\n
\n\n\n\n\n\n
\n
\n\n\n\n\n
\n
\n\n
\n
\n  \n 2021\n \n \n (2)\n \n \n
\n
\n \n \n
\n
\n  \n 2\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n Deepesh Data; Linqi Song; and Suhas N. Diggavi.\n\n\n \n \n \n \n \n Data Encoding for Byzantine-Resilient Distributed Optimization.\n \n \n \n \n\n\n \n\n\n\n IEEE Transactions on Information Theory, 67(2): 1117-1140. Feb 2021.\n \n\n\n\n
\n\n\n\n \n \n \"Data arxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 3 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@article{DBLP:journals/corr/abs-1907-02664,\n abstract = {We study distributed optimization in the presence of Byzantine adversaries, where both data and computation are distributed among m worker machines, t of which may be corrupt. The compromised nodes may collaboratively and arbitrarily deviate from their pre-specified programs, and a designated (master) node iteratively computes the model/parameter vector for generalized linear models. In this work, we primarily focus on two iterative algorithms: Proximal Gradient Descent (PGD) and Coordinate Descent (CD). Gradient descent (GD) is a special case of these algorithms. PGD is typically used in the data-parallel setting, where data is partitioned across different samples, whereas, CD is used in the model-parallelism setting, where data is partitioned across the parameter space.  In this paper, we propose a method based on data encoding and error correction over real numbers to combat adversarial attacks. We can tolerate up to t≤⌊m−12⌋ corrupt worker nodes, which is information-theoretically optimal. We give deterministic guarantees, and our method does not assume any probability distribution on the data. We develop a {\\em sparse} encoding scheme which enables computationally efficient data encoding and decoding. We demonstrate a trade-off between the corruption threshold and the resource requirements (storage, computational, and communication complexity). As an example, for t≤m3, our scheme incurs only a {\\em constant} overhead on these resources, over that required by the plain distributed PGD/CD algorithms which provide no adversarial protection. To the best of our knowledge, ours is the first paper that makes CD secure against adversarial attacks.  Our encoding scheme extends efficiently to the data streaming model and for stochastic gradient descent (SGD). We also give experimental results to show the efficacy of our proposed schemes.},\n author = {Deepesh Data and\nLinqi Song and\nSuhas N. Diggavi},\n eprint = {1907.02664},\n journal = {IEEE Transactions on Information Theory},\n tags = {journal,SDL,DML},\n title = {Data Encoding for Byzantine-Resilient Distributed Optimization},\n type = {2},\n url_arxiv = {http://arxiv.org/abs/1907.02664},\n volume = {},\n year = {2021},\n volume={67},\n number={2},\n pages={1117-1140},\n doi = {10.1109/TIT.2020.3035868},\n ISSN={1557-9654},\n month={Feb},\n}\n\n
\n
\n\n\n
\n We study distributed optimization in the presence of Byzantine adversaries, where both data and computation are distributed among m worker machines, t of which may be corrupt. The compromised nodes may collaboratively and arbitrarily deviate from their pre-specified programs, and a designated (master) node iteratively computes the model/parameter vector for generalized linear models. In this work, we primarily focus on two iterative algorithms: Proximal Gradient Descent (PGD) and Coordinate Descent (CD). Gradient descent (GD) is a special case of these algorithms. PGD is typically used in the data-parallel setting, where data is partitioned across different samples, whereas, CD is used in the model-parallelism setting, where data is partitioned across the parameter space. In this paper, we propose a method based on data encoding and error correction over real numbers to combat adversarial attacks. We can tolerate up to t≤⌊m−12⌋ corrupt worker nodes, which is information-theoretically optimal. We give deterministic guarantees, and our method does not assume any probability distribution on the data. We develop a \\em sparse encoding scheme which enables computationally efficient data encoding and decoding. We demonstrate a trade-off between the corruption threshold and the resource requirements (storage, computational, and communication complexity). As an example, for t≤m3, our scheme incurs only a \\em constant overhead on these resources, over that required by the plain distributed PGD/CD algorithms which provide no adversarial protection. To the best of our knowledge, ours is the first paper that makes CD secure against adversarial attacks. Our encoding scheme extends efficiently to the data streaming model and for stochastic gradient descent (SGD). We also give experimental results to show the efficacy of our proposed schemes.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 4\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n Deepesh Data; and Suhas Diggavi.\n\n\n \n \n \n \n \n Byzantine-Resilient High-Dimensional SGD with Local Iterations on Heterogeneous Data.\n \n \n \n \n\n\n \n\n\n\n Proceedings International Conference on Machine Learning (ICML). 2021.\n \n\n\n\n
\n\n\n\n \n \n \"Byzantine-Resilient arxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 3 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@article{data2020byzantine2,\n abstract = {We study stochastic gradient descent (SGD) with local iterations in the presence of malicious/Byzantine clients, motivated by the federated learning. The clients, instead of communicating with the central server in every iteration, maintain their local models, which they update by taking several SGD iterations based on their own datasets and then communicate the net update with the server, thereby achieving communication-efficiency. Furthermore, only a subset of clients communicate with the server, and this subset may be different at different synchronization times. The Byzantine clients may collaborate and send arbitrary vectors to the server to disrupt the learning process. To combat the adversary, we employ an efficient high-dimensional robust mean estimation algorithm from Steinhardt et al.~\\cite[ITCS 2018]{Resilience_SCV18} at the server to filter-out corrupt vectors; and to analyze the outlier-filtering procedure, we develop a novel matrix concentration result that may be of independent interest. \nWe provide convergence analyses for strongly-convex and non-convex smooth objectives in the heterogeneous data setting, where different clients may have different local datasets, and we do not make any probabilistic assumptions on data generation. We believe that ours is the first Byzantine-resilient algorithm and analysis with local iterations. We derive our convergence results under minimal assumptions of bounded variance for SGD and bounded gradient dissimilarity (which captures heterogeneity among local datasets). We also extend our results to the case when clients compute full-batch gradients.},\n author = {Data, Deepesh and Diggavi, Suhas},\n journal = {Proceedings International Conference on Machine Learning (ICML)},\n tags = {conf,SDL,DML},\n title = {Byzantine-Resilient High-Dimensional SGD with Local Iterations on Heterogeneous Data},\n type = {4},\n url_arxiv = {https://arxiv.org/abs/2006.13041},\n year = {2021}\n}\n\n
\n
\n\n\n
\n We study stochastic gradient descent (SGD) with local iterations in the presence of malicious/Byzantine clients, motivated by the federated learning. The clients, instead of communicating with the central server in every iteration, maintain their local models, which they update by taking several SGD iterations based on their own datasets and then communicate the net update with the server, thereby achieving communication-efficiency. Furthermore, only a subset of clients communicate with the server, and this subset may be different at different synchronization times. The Byzantine clients may collaborate and send arbitrary vectors to the server to disrupt the learning process. To combat the adversary, we employ an efficient high-dimensional robust mean estimation algorithm from Steinhardt et al. i̧te[ITCS 2018]Resilience_SCV18 at the server to filter-out corrupt vectors; and to analyze the outlier-filtering procedure, we develop a novel matrix concentration result that may be of independent interest. We provide convergence analyses for strongly-convex and non-convex smooth objectives in the heterogeneous data setting, where different clients may have different local datasets, and we do not make any probabilistic assumptions on data generation. We believe that ours is the first Byzantine-resilient algorithm and analysis with local iterations. We derive our convergence results under minimal assumptions of bounded variance for SGD and bounded gradient dissimilarity (which captures heterogeneity among local datasets). We also extend our results to the case when clients compute full-batch gradients.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n\n\n\n
\n
\n\n
\n
\n  \n 2020\n \n \n (2)\n \n \n
\n
\n \n \n
\n
\n  \n 1\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n Deepesh Data; and Suhas Diggavi.\n\n\n \n \n \n \n \n Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data.\n \n \n \n \n\n\n \n\n\n\n arXiv preprint arXiv:2005.07866. 2020.\n \n\n\n\n
\n\n\n\n \n \n \"Byzantine-Resilient arxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@article{data2020byzantine1,\n abstract = {We study distributed stochastic gradient descent (SGD) in the master-worker architecture under Byzantine attacks. We consider the heterogeneous data model, where different workers may have different local datasets, and we do not make any probabilistic assumptions on data generation. At the core of our algorithm, we use the polynomial-time outlier-filtering procedure for robust mean estimation proposed by Steinhardt et al. (ITCS 2018) to filter-out corrupt gradients. In order to be able to apply their filtering procedure in our {\\em heterogeneous} data setting where workers compute {\\em stochastic} gradients, we derive a new matrix concentration result, which may be of independent interest. \nWe provide convergence analyses for smooth strongly-convex and non-convex objectives. We derive our results under the bounded variance assumption on local stochastic gradients and a {\\em deterministic} condition on datasets, namely, gradient dissimilarity; and for both these quantities, we provide concrete bounds in the statistical heterogeneous data model. We give a trade-off between the mini-batch size for stochastic gradients and the approximation error. Our algorithm can tolerate up to 14 fraction Byzantine workers. It can find approximate optimal parameters in the strongly-convex setting exponentially fast and reach to an approximate stationary point in the non-convex setting with a linear speed, thus, matching the convergence rates of vanilla SGD in the Byzantine-free setting. \nWe also propose and analyze a Byzantine-resilient SGD algorithm with gradient compression, where workers send k random coordinates of their gradients. Under mild conditions, we show a d/k-factor saving in communication bits as well as decoding complexity over our compression-free algorithm without affecting its convergence rate (order-wise) and the approximation error.},\n author = {Data, Deepesh and Diggavi, Suhas},\n journal = {arXiv preprint arXiv:2005.07866},\n tags = {journalSub,SDL,DML},\n title = {Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data},\n type = {1},\n url_arxiv = {https://arxiv.org/abs/2005.07866},\n year = {2020}\n}\n\n
\n
\n\n\n
\n We study distributed stochastic gradient descent (SGD) in the master-worker architecture under Byzantine attacks. We consider the heterogeneous data model, where different workers may have different local datasets, and we do not make any probabilistic assumptions on data generation. At the core of our algorithm, we use the polynomial-time outlier-filtering procedure for robust mean estimation proposed by Steinhardt et al. (ITCS 2018) to filter-out corrupt gradients. In order to be able to apply their filtering procedure in our \\em heterogeneous data setting where workers compute \\em stochastic gradients, we derive a new matrix concentration result, which may be of independent interest. We provide convergence analyses for smooth strongly-convex and non-convex objectives. We derive our results under the bounded variance assumption on local stochastic gradients and a \\em deterministic condition on datasets, namely, gradient dissimilarity; and for both these quantities, we provide concrete bounds in the statistical heterogeneous data model. We give a trade-off between the mini-batch size for stochastic gradients and the approximation error. Our algorithm can tolerate up to 14 fraction Byzantine workers. It can find approximate optimal parameters in the strongly-convex setting exponentially fast and reach to an approximate stationary point in the non-convex setting with a linear speed, thus, matching the convergence rates of vanilla SGD in the Byzantine-free setting. We also propose and analyze a Byzantine-resilient SGD algorithm with gradient compression, where workers send k random coordinates of their gradients. Under mild conditions, we show a d/k-factor saving in communication bits as well as decoding complexity over our compression-free algorithm without affecting its convergence rate (order-wise) and the approximation error.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 4\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n Deepesh Data; and Suhas Diggavi.\n\n\n \n \n \n \n On Byzantine-Resilient High-Dimensional Stochastic Gradient Descent.\n \n \n \n\n\n \n\n\n\n In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2628–2633, 2020. IEEE\n \n\n\n\n
\n\n\n\n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@inproceedings{data2020byzantine,\n abstract = {We study stochastic gradient descent (SGD) in the master-worker architecture under Byzantine attacks. Building upon the recent advances in algorithmic high-dimensional robust statistics, in each SGD iteration, master employs a non-trivial decoding to estimate the true gradient from the unbiased stochastic gradients received from workers, some of which may be corrupt. We provide convergence analyses for both strongly-convex and non-convex smooth objectives under standard SGD assumptions. We can control the approximation error of our solution in both these settings by the mini-batch size of stochastic gradients; and we can make the approximation error as small as we want, provided that workers use a sufficiently large mini-batch size. Our algorithm can tolerate less than 1/3 fraction of Byzantine workers. It can approximately find the optimal parameters in the strongly-convex setting exponentially fast, and reaches to an approximate stationary point in the non-convex setting with linear speed, i.e., with a rate of 1/T, thus, matching the convergence rates of vanilla SGD in the Byzantine-free setting.},\n author = {Data, Deepesh and Diggavi, Suhas},\n booktitle = {2020 IEEE International Symposium on Information Theory (ISIT)},\n organization = {IEEE},\n pages = {2628--2633},\n tags = {conf,SDL,DML},\n title = {On Byzantine-Resilient High-Dimensional Stochastic Gradient Descent},\n type = {4},\n doi = {10.1109/ISIT44484.2020.9174363},\n year = {2020}\n}\n\n
\n
\n\n\n
\n We study stochastic gradient descent (SGD) in the master-worker architecture under Byzantine attacks. Building upon the recent advances in algorithmic high-dimensional robust statistics, in each SGD iteration, master employs a non-trivial decoding to estimate the true gradient from the unbiased stochastic gradients received from workers, some of which may be corrupt. We provide convergence analyses for both strongly-convex and non-convex smooth objectives under standard SGD assumptions. We can control the approximation error of our solution in both these settings by the mini-batch size of stochastic gradients; and we can make the approximation error as small as we want, provided that workers use a sufficiently large mini-batch size. Our algorithm can tolerate less than 1/3 fraction of Byzantine workers. It can approximately find the optimal parameters in the strongly-convex setting exponentially fast, and reaches to an approximate stationary point in the non-convex setting with linear speed, i.e., with a rate of 1/T, thus, matching the convergence rates of vanilla SGD in the Byzantine-free setting.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n\n\n\n
\n
\n\n
\n
\n  \n 2019\n \n \n (1)\n \n \n
\n
\n \n \n
\n
\n  \n 4\n \n \n (2)\n \n \n
\n
\n \n \n
\n \n\n \n \n Deepesh Data; and Suhas Diggavi.\n\n\n \n \n \n \n Byzantine-Tolerant Distributed Coordinate Descent.\n \n \n \n\n\n \n\n\n\n In 2019 IEEE International Symposium on Information Theory (ISIT), pages 2724–2728, 2019. IEEE\n \n\n\n\n
\n\n\n\n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@inproceedings{data2019byzantine,\n abstract = {We study distributed coordinate descent (CD) in the master-worker architecture under adversarial attacks, where the data is partitioned (across the parameter space) and distributed among m worker nodes (t of which can be maliciously corrupt), which update some coordinates of their part of the parameter vector, in parallel and iteratively, using CD updates, with the help of the master. We propose a method based on data encoding and real error correction to combat the adversary. Our method can tolerate up to ⌈m-1/2⌉ corrupt nodes, which is information-theoretically optimal. Our design gives a trade-off between the resiliency t, the required redundancy, and the computation at master and worker nodes. For example, with constant overhead in the storage and computational complexity over that required by the plain distributed CD, we can tolerate up to m/3 corrupt nodes. We design a sparse encoding scheme, which yields low encoding complexity.},\n author = {Data, Deepesh and Diggavi, Suhas},\n booktitle = {2019 IEEE International Symposium on Information Theory (ISIT)},\n organization = {IEEE},\n pages = {2724--2728},\n tags = {conf,SDL,DML},\n title = {Byzantine-Tolerant Distributed Coordinate Descent},\n type = {4},\n doi = {10.1109/ISIT.2019.8849217},\n year = {2019}\n}\n\n
\n
\n\n\n
\n We study distributed coordinate descent (CD) in the master-worker architecture under adversarial attacks, where the data is partitioned (across the parameter space) and distributed among m worker nodes (t of which can be maliciously corrupt), which update some coordinates of their part of the parameter vector, in parallel and iteratively, using CD updates, with the help of the master. We propose a method based on data encoding and real error correction to combat the adversary. Our method can tolerate up to ⌈m-1/2⌉ corrupt nodes, which is information-theoretically optimal. Our design gives a trade-off between the resiliency t, the required redundancy, and the computation at master and worker nodes. For example, with constant overhead in the storage and computational complexity over that required by the plain distributed CD, we can tolerate up to m/3 corrupt nodes. We design a sparse encoding scheme, which yields low encoding complexity.\n
\n\n\n
\n\n\n
\n \n\n \n \n Deepesh Data; Linqi Song; and Suhas Diggavi.\n\n\n \n \n \n \n Data encoding methods for byzantine-resilient distributed optimization.\n \n \n \n\n\n \n\n\n\n In 2019 IEEE International Symposium on Information Theory (ISIT), pages 2719–2723, 2019. IEEE\n \n\n\n\n
\n\n\n\n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@inproceedings{data2019data,\n abstract = {We consider distributed gradient computation, where both data and computation are distributed among m worker machines, t of which can be Byzantine adversaries, and a designated (master) node computes the model/parameter vector for generalized linear models, iteratively, using proximal gradient descent (PGD), of which gradient descent (GD) is a special case. The Byzantine adversaries can (collaboratively) deviate arbitrarily from their gradient computation. To solve this, we propose a method based on data encoding and (real) error correction to combat the adversarial behavior. We can tolerate up to t ≤ [m-1/2] corrupt worker nodes, which is information-theoretically optimal. Our method does not assume any probability distribution on the data. We develop a sparse encoding scheme which enables computationally efficient data encoding. We demonstrate a trade-off between the number of adversaries tolerated and the resource requirement (storage and computational complexity). As an example, our scheme incurs a constant overhead (storage and computational complexity) over that required by the distributed PGD algorithm, without adversaries, for t ≤ m/3 . Our encoding works as efficiently in the streaming data etting as it does in the},\n author = {Data, Deepesh and Song, Linqi and Diggavi, Suhas},\n booktitle = {2019 IEEE International Symposium on Information Theory (ISIT)},\n organization = {IEEE},\n pages = {2719--2723},\n tags = {conf,SDL,DML},\n title = {Data encoding methods for byzantine-resilient distributed optimization},\n type = {4},\n doi = {10.1109/ISIT.2019.8849857},\n year = {2019}\n}\n\n
\n
\n\n\n
\n We consider distributed gradient computation, where both data and computation are distributed among m worker machines, t of which can be Byzantine adversaries, and a designated (master) node computes the model/parameter vector for generalized linear models, iteratively, using proximal gradient descent (PGD), of which gradient descent (GD) is a special case. The Byzantine adversaries can (collaboratively) deviate arbitrarily from their gradient computation. To solve this, we propose a method based on data encoding and (real) error correction to combat the adversarial behavior. We can tolerate up to t ≤ [m-1/2] corrupt worker nodes, which is information-theoretically optimal. Our method does not assume any probability distribution on the data. We develop a sparse encoding scheme which enables computationally efficient data encoding. We demonstrate a trade-off between the number of adversaries tolerated and the resource requirement (storage and computational complexity). As an example, our scheme incurs a constant overhead (storage and computational complexity) over that required by the distributed PGD algorithm, without adversaries, for t ≤ m/3 . Our encoding works as efficiently in the streaming data etting as it does in the\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n\n\n\n
\n
\n\n
\n
\n  \n 2018\n \n \n (1)\n \n \n
\n
\n \n \n
\n
\n  \n 4\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n Deepesh Data; Linqi Song; and Suhas Diggavi.\n\n\n \n \n \n \n Data encoding for Byzantine-resilient distributed gradient descent.\n \n \n \n\n\n \n\n\n\n In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 863–870, 2018. IEEE\n \n\n\n\n
\n\n\n\n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@inproceedings{data2018data,\n abstract = {We consider distributed gradient computation, where both data and computation are distributed among m worker machines, t of which can be Byzantine adversaries, and a designated (master) node computes the model/parameter vector, iteratively using gradient descent (GD). The Byzantine adversaries can (collaboratively) deviate arbitrarily from their gradient computation. To solve this, we propose a method based on data encoding and (real) error correction to combat the adversarial behavior. We can tolerate up to t ≤ [m-1/2] corrupt worker nodes, which is information-theoretically optimal. Our method does not assume any probability distribution on the data. We develop a sparse encoding scheme which enables computationally efficient data encoding. We demonstrate a trade-off between the number of adversaries tolerated and the resource requirement (storage and computational complexity). As an example, our scheme incurs a constant overhead (storage and computational complexity) over that required by the distributed GD algorithm, without adversaries, for t ≤ m/3.},\n author = {Data, Deepesh and Song, Linqi and Diggavi, Suhas},\n booktitle = {2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton)},\n organization = {IEEE},\n pages = {863--870},\n tags = {conf,SDL,DML},\n title = {Data encoding for Byzantine-resilient distributed gradient descent},\n type = {4},\n doi = {10.1109/ALLERTON.2018.8636017},\n year = {2018}\n}\n\n
\n
\n\n\n
\n We consider distributed gradient computation, where both data and computation are distributed among m worker machines, t of which can be Byzantine adversaries, and a designated (master) node computes the model/parameter vector, iteratively using gradient descent (GD). The Byzantine adversaries can (collaboratively) deviate arbitrarily from their gradient computation. To solve this, we propose a method based on data encoding and (real) error correction to combat the adversarial behavior. We can tolerate up to t ≤ [m-1/2] corrupt worker nodes, which is information-theoretically optimal. Our method does not assume any probability distribution on the data. We develop a sparse encoding scheme which enables computationally efficient data encoding. We demonstrate a trade-off between the number of adversaries tolerated and the resource requirement (storage and computational complexity). As an example, our scheme incurs a constant overhead (storage and computational complexity) over that required by the distributed GD algorithm, without adversaries, for t ≤ m/3.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n\n\n\n
\n
\n\n\n\n\n
\n\n\n \n\n \n \n \n \n\n
\n"}; document.write(bibbase_data.data);